package com.lw.leetcode.binary.b;

/**
 * Created with IntelliJ IDEA.
 * 2064. 分配给商店的最多商品的最小值
 *
 * @author liw
 * @version 1.0
 * @date 2022/3/22 13:26
 */
public class MinimizedMaximum {

    public static void main(String[] args) {
        MinimizedMaximum test = new MinimizedMaximum();

        // 3
//        int[] arr = {11, 6};
//        int n = 6;

        // 5
//        int[] arr = {15,10,10};
//        int n = 7;

        // 100000
        int[] arr = {10000};
        int n = 1;

        int i = test.minimizedMaximum(n, arr);
        System.out.println(i);

    }

    public int minimizedMaximum(int n, int[] quantities) {
        int st = 1;
        int end = 0;
        for (int quantity : quantities) {
            end = Math.max(end, quantity);
        }
        while (st < end) {
            int m = st + ((end - st) >> 1);
            int sum = 0;
            int s = m - 1;
            for (int v : quantities) {
                sum += (v + s) / m;
            }
            if (sum > n) {
                st = m + 1;
            } else {
                end = m;
            }
        }
        return st;
    }

}
